Chuỗi thức ăn

Buổi 25 — Disjoint Set Union Data-structures
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Trong một khu rừng có $N$ loài vật (đánh số $1..N$) thuộc 3 nhóm $A, B, C$ theo quy luật chuỗi thức ăn vòng tròn: $A$ ăn $B$, $B$ ăn $C$, và $C$ ăn $A$. Có $Q$ phát biểu được đưa ra lần lượt:

  • 1 x y: Loài $x$ và $y$ thuộc cùng một nhóm.
  • 2 x y: Loài $x$ ăn loài $y$.

Một phát biểu là sai nếu nó mâu thuẫn với các phát biểu đúng trước đó, hoặc nếu $x = y$ trong phát biểu loại 2. Hãy đếm tổng số phát biểu sai.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • $Q$ dòng tiếp theo chứa các phát biểu (1 x y hoặc 2 x y, $1 \le x, y \le N$).
Dữ liệu ra
  • Một số nguyên duy nhất là số lượng phát biểu sai.
Ví dụ
Input Output
5 5
1 1 2
2 2 3
2 3 4
2 4 1
1 1 4
1
Giới hạn
  • $1 \le N, Q \le 10^5$
Draft saved