Quan hệ bạn và thù

General
Points
58
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có $N$ người (đánh số $1..N$) và $M$ phát biểu tuần tự (đánh số $1..M$). Mỗi phát biểu có một trong hai dạng:

  • F u v: $u$ và $v$ là bạn.
  • E u v: $u$ và $v$ là kẻ thù.

Quy tắc bắc cầu như sau: bạn của bạn là bạn; kẻ thù của kẻ thù là bạn; bạn của kẻ thù (hoặc kẻ thù của bạn) là kẻ thù. Không ai có thể vừa là bạn vừa là kẻ thù của cùng một người (và mỗi người luôn là bạn của chính mình). Hãy tìm chỉ số (1-based) của phát biểu đầu tiên gây ra mâu thuẫn với các phát biểu trước đó, hoặc -1 nếu tất cả đều hợp lý.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ký tự F hoặc E và hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
  • Một số nguyên duy nhất là chỉ số phát biểu mâu thuẫn đầu tiên, hoặc -1.
Ví dụ
Input Output
4 4
F 1 2
E 2 3
E 3 4
E 1 4
4
3 3
F 1 2
E 2 3
E 1 3
-1
Giới hạn
  • $1 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$
Draft saved