마법봉
면접 대비시간 제한1초메모리 제한512 MB
각 대결의 승자가 정해져 있을 때 대결 순서를 자유롭게 정해서, 처음에 마법사 1이 쥔 지팡이가 모든 대결이 끝난 뒤 누구에게 있을 수 있는지 판별한다.
문제
Kile은 Nikola가 만든 마법사와 마법봉 문제를 아주 좋아해서 직접 변형한 문제를 만들기로 했다. 그는 마법사 26명 대신 1부터 N까지의 정수로 번호가 붙은 마법사 N명이 있고, 마법사들 사이에서 M번의 결투가 열린다고 상상했다. 같은 두 마법사 사이의 결투가 여러 번 열릴 수도 있다.
Nikola의 문제에서처럼 결투 전에 마법봉을 패자가 가지고 있었다면, 결투가 끝난 뒤 마법봉은 승자에게 넘어간다.
각 결투에서 어느 두 마법사가 싸우는지, 그리고 그중 누가 이기는지를 미리 알고 있고 결투를 치르는 순서를 우리가 정할 수 있다면, Kile은 M번의 결투가 모두 끝난 뒤 마법봉이 누구 손에 있을 수 있는지 알고 싶어 한다.
처음에 마법봉은 번호가 1인 마법사가 가지고 있다.
입력
첫째 줄에 두 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100 000)
다음 M개 줄에 두 수 Xi와 Yi가 주어진다. (1 ≤ Xi, Yi ≤ N, Xi ≠ Yi) 마법사 Xi가 마법사 Yi를 이긴다.
출력
첫째 줄에 N개의 문자를 출력한다. k번째 문자는 번호가 k인 마법사가 M번의 결투가 모두 끝난 뒤 마법봉을 가질 수 있으면 '1', 아니면 '0'이다.