시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 43 19 8 29.630%

문제

BOJ 행성에는 N마리의 동물들이 살고 있습니다. 민호는 이 동물들을 구분하기 위해 1, 2, ..., N의 번호를 붙였습니다. 또한 BOJ 행성에 살고 있는 모든 동물들은 A, B, C의 세 종류 중 하나입니다. 민호는 재미있는 점을 발견 했는데 A는 B를 먹고 B는 C를 먹고 C는 A를 먹는다는 사실 입니다.

오랜 기간 행성을 관찰한 민호는 자신이 기록한 내용을 기반으로 BOJ 행성의 생태 지도를 그려보려 합니다. 민호가 기록한 내용은 아래 두 종류 중 하나입니다.

  • 타입 1: x와 y는 같은 종류입니다.
  • 타입 2: x는 y를 먹습니다.

K개의 기록을 1번부터 2번, 3번 … K번까지 순서대로 참고하여 생태 지도를 그려가던 중, 민호는 이제까지 그려온 생태 지도와 모순되는 경우나 x와 y가 올바른 동물의 번호가 아닌 경우가 있다는 것을 발견했습니다.

어디서부터 잘못된 건지 찾기 힘들었던 민호는 1번부터 K번까지의 기록을 따라 생태 지도를 그리다 잘못된 기록을 만나면 그 기록은 넘어가기로 했습니다.

민호가 그냥 넘어가야 할 정보는 총 몇 개인지 계산하는 프로그램을 작성해 봅시다.

입력

첫째 줄에는 N, K (1 ≤ N ≤ 50,000, 0 ≤ K ≤ 100,000) 이 공백을 구분으로 주어집니다.

각각은 동물의 수와 민호가 기록한 내용의 수를 의비합니다.

두 번째 줄부터 K개의 줄에 걸쳐 민호가 기록한 내용이 주어집니다. 각각의 기록은 ti, xi, yi입니다. ti는 1 또는 2이며 xi, yi는 32비트 부호있는 정수중 하나입니다.

출력

민호가 건너 뛰어야 할 잘못된 기록의 수를 출력합니다.

예제 입력 1

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

예제 출력 1

3

출처

  • 어색한 표현을 찾은 사람: jh05013