루도
시간 제한2초메모리 제한1024 MB
어떤 경로에서도 같은 정점을 다시 지나지 않는 그래프에서, 말을 방문하지 않은 이웃으로 옮기는 게임을 각 시작 정점마다 먼저 두는 사람이 이기는지 판정한다.
문제
시장에 새로운 게임이 나왔다. 잘 알려진 게임 "화내지 마세요!"를 변형한 것으로, "루도"라고도 부른다. Deni와 Bob은 곧바로 이 게임을 사서 규칙을 익히기 시작했다. 1번부터 N번까지 번호가 붙은 칸이 있는 지도가 주어진다. 일부 칸 쌍은 서로 이웃이다. 말이 하나 있는데, 이 말은 어떤 칸에 놓을 수 있고 어떤 칸에서 이웃한 칸으로 옮길 수 있다.
이 지도에는 특별한 성질이 있다. 어떤 칸에서 출발해도, 이미 지나온 칸을 다시 거치지 않고서는 같은 칸으로 돌아올 수 없다. 첫 번째 플레이어가 말을 어느 칸에 놓을지 정한다. 그다음은 두 번째 플레이어의 차례이고, 두 플레이어는 번갈아 가며 말을 어떤 칸에서 이웃한 칸으로 옮긴다. 말이 방문한 칸은 모두 표시되고, 말은 그 칸을 다시 밟을 수 없다. 이웃한 칸 중 표시되지 않은 칸으로 말을 옮길 수 없는 플레이어가 지고, 상대 플레이어가 이긴다. Deni와 Bob은 이런 게임에 경험이 많아서 항상 최적으로 둔다. Deni가 첫 수를 둔다. Deni는 말을 처음 놓을 칸을 잘 골라서 이길 수 있다.
프로그램 ludo를 작성해 게임의 조건을 읽고, 각 칸이 첫 번째로 두는 플레이어에게 이기는 위치인지 지는 위치인지 판별하라.
입력
표준 입력의 첫 줄에서 프로그램은 두 양의 정수 N과 M을 읽는다. N은 지도의 칸 수, M은 서로 이웃인 칸 쌍의 수이다. 다음 M개 줄 각각에서 프로그램은 두 정수 x와 y를 읽는데, 이는 x번 칸과 y번 칸이 서로 이웃이라는 뜻이다.
출력
칸 번호 순서대로, 공백 없이 0과 1로 이루어진 문자열을 출력하라. 0은 첫 번째 플레이어에게 지는 위치, 1은 이기는 위치이다.
제한
- 1 ≤ N ≤ 5∙10^5
- 1 ≤ M ≤ 5∙10^5
힌트
이 출력은 최적으로 두는 게임에서 Deni가 1, 2, 3번 칸에 말을 놓으면 지고, 나머지 모든 칸에서는 이긴다는 뜻이다. Deni가 1번 칸에 말을 놓으면 Bob은 말을 3번 칸으로 옮길 수 있고, 1번 칸은 이미 표시되어 있으므로 Deni는 더 둘 수가 없다. 마찬가지로 Deni가 2번 칸에 말을 놓아도 진다. 4번과 5번 칸에서는 Deni에게 이기는 전략이 있다.