바이토치 마을 현대화
시간 제한3초메모리 제한1024 MB
두 명 중 한 명에게 컴퓨터가 전달되는 사건, 고장 사건, 질의를 차례로 처리하여 각 주민이 확실히 가졌는지, 확실히 없는지, 불확실한지 판별합니다.
문제
바이토치 지역의 한 마을이 현대화되고 있다. 정부의 최신 사업 목표는 컴퓨터가 없는 마을과 소도시 주민에게 컴퓨터를 공급하는 것이다. 바이타자르는 이 사업 대상 마을 중 하나인 바이토슈치의 현대화를 맡고 있다. 바이토슈치에는 현재 컴퓨터를 가진 주민이 한 명도 없다.
바이토슈치에는 n명의 주민이 살고 있으며, 바이타자르는 편의상 1부터 n까지 번호를 붙였다. 처음에는 아무도 컴퓨터가 없다. 바이타자르는 세 종류의 사건을 처리해야 한다.
+ ai bi: 바이토슈치의 주민 한 명에게 컴퓨터가 배달된다. 바이타자르는 그 컴퓨터가 ai번 주민에게 갔는지 bi번 주민에게 갔는지 알지 못한다. ai = bi이면 컴퓨터는 확실히 ai번 주민에게 간 것이다. 컴퓨터는 항상 지금 컴퓨터가 없는 주민에게 배달된다.
- ci: ci번 주민의 컴퓨터가 고장 난다. 이 주민은 전에 컴퓨터를 갖고 있었던 것이 확실하다. 고장 난 뒤에는 컴퓨터가 없으며, 나중에 새 컴퓨터를 받을 수도 있다.
? di: 바이타자르는 지금까지 얻은 정보를 모두 바탕으로, di번 주민이 확실히 컴퓨터를 갖고 있는지, 확실히 갖고 있지 않은지, 갖고 있을 수도 있고 없을 수도 있는지 판단해야 한다.
입력
첫 줄에 두 정수 n과 q가 주어진다(n은 1 이상 300,000 이하, q는 1 이상 1,000,000 이하). n은 주민 수, q는 사건 수이다. 이어지는 q개의 줄에 위에서 설명한 사건이 한 줄에 하나씩 주어진다. 모든 사건에서 ai, bi, ci, di는 1 이상 n 이하이다.
'?' 사건이 적어도 한 번 있다는 것이 보장된다. 또한 컴퓨터가 항상 지금 컴퓨터가 없는 주민에게 배달되고, 컴퓨터가 항상 지금 갖고 있는 주민에게서만 고장 나는 배달 과정이 적어도 하나 존재한다는 것이 보장된다.
출력
'?' 사건의 개수와 같은 길이의 문자열을 출력한다. i번째 '?' 사건에서 해당 주민이 확실히 컴퓨터를 갖고 있으면 i번째 문자는 '1', 확실히 갖고 있지 않으면 '0', 갖고 있을 수도 있고 없을 수도 있으면 '?'이다.
힌트
예시 설명: 처음에는 아무도 컴퓨터가 없으므로 첫 번째 질문의 답은 아니오이고, 첫 출력 문자는 '0'이다. 이후 컴퓨터 두 대가 배달되고, 두 번째 주민이 컴퓨터를 갖고 있는지 묻는다. 앞의 두 번의 배달 중 하나가 그 주민에게 갔을 수도 있다. 하지만 첫 번째 주민과 세 번째 주민에게 각각 갔을 수도 있다. 따라서 판단할 수 없고 답은 '?'이다. 다음 배달 이후에는 두 번째 주민이 이미 컴퓨터를 갖고 있었던 것이 분명해지지만, 질문 시점에 바이타자르는 이를 알 수 없었다.