VM 11 Bài 09 - Đồ thị 3 phía

View as PDF

Submit solution

Points: 1.63 (partial)
Time limit: 0.6s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VM11 - Tác giả: Lê Ðôn Khuê
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một đồ thị vô hướng được gọi là đồ thị 3 phía nếu tồn tại một cách chia tập đỉnh ~V~ thành ~3~ tập ~V_1~, ~V_2~, ~V_3~ khác rỗng sao cho mọi cặp đỉnh ~\left(u, v\right)~ có cạnh nối thì ~u, v~ thuộc ~2~ tập con khác nhau. Cho đồ thị ~G=<V, E>~ là một đồ thị ~3~ phía, tìm cách chia tập ~V~ thành ~3~ tập ~V_1~, ~V_2~, ~V_3~ khác rỗng thỏa mãn.

Input

  • Dòng đầu tiên ghi hai số ~N~ và ~M~ trong đó ~N~ là số đỉnh của đồ thị, ~M~ là số cạnh của đồ thị.
  • ~M~ dòng tiếp theo, mỗi dòng ghi ~2~ số ~u~, ~v~ thể hiện cạnh nối giữa ~u~ và ~v~. ~\left(u \ne v\right)~

Output

  • In ra xâu ~N~ kí tự. Kí tự thứ ~i~ là ~1/2/3~ tương ứng với đỉnh ~i~ thuộc tập ~V_1/V_2/V_3~.
  • Dữ liệu đảm bảo luôn có đáp án. Bạn chỉ cần đưa ra một đáp án bất kỳ.

Giới hạn

~3 \le N \le 200~, trong ~20\%~ số test có ~N \le 15~.

Sample Input

5 6
1 2
1 5
1 4
2 3
3 5
5 4

Sample Output

12132

Comments

Please read the guidelines before commenting.


There are no comments at the moment.