무리에는 항상 말썽꾼이 있습니다. Farmer John은 소 $N$마리 ($1 \le N \le 100$, 번호1부터 $N$) 중 하나가 항상 거짓말하고 나머지는 항상 진실임을 알아냈습니다. 빨리 찾으려고 방목 중인 소를 하나씩 방문해 먹는 양에 대한 간단한 질문 $Q$개 ($1 \le Q \le 1{,}000$)를 합니다 (소는 대체로 정직하지만 똑똑하지 않고 먹이는 이해하는 드문 주제입니다). 다음처럼 기록합니다:

소4는5가10보다 풀을 많이 먹는다고 합니다. 소6는10이7보다 많이 먹는다고 합니다. 소3은2가6보다 많이 먹는다고 합니다. 소1은7이5보다 많이 먹는다고 합니다.

위 거짓말쟁이는4, 6, 1 중 하나입니다. 응답으로 가능한 거짓말쟁이 수를 구하세요. 입력상 유일한 거짓말쟁이가 될 수 있는 소입니다.

입력

• 1행: 공백으로 구분한 두 정수 $N$, $Q$.
• $2..Q+1$행: 각 응답은 공백으로 구분한 세 정수 $A$, $B$, $C$입니다. 소 $A$가 소 $B$는 소 $C$보다 풀을 많이 먹는다고 합니다. 같은 소가 여러 번 나올 수 있습니다.

출력

• 1행: 가능한 거짓말쟁이 수인 한 정수.

예제

입력 1

3 4
3 1 2
1 3 1
1 3 2
2 2 1

출력 1

2

참고

입력 설명

3소가4응답을 줍니다. 소1은3이1과2보다 많이 먹는다, 소2는2가1보다 많이 먹는다, 소3은1이2보다 많이 먹는다고 합니다 (먹는 양의 비교입니다).

출력 설명

2나3은 반대 말을 하므로 하나가 거짓입니다. 1이 거짓이라면2와3 모두 거짓일 수 없으므로1은 진실입니다.

문제 작성자: Brian Dean, 2004