Chuỗi thức ăn
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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 yhoặc2 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$
Community Discussion