탐색

0번부터 n − 1번까지 번호가 붙은 n개의 노드로 이루어진 그래프가 주어질 때, 몇 가지 연산을 사용해 m개의 무향 간선을 모두 찾아야 한다.

각 노드에는 표시 w가 있고, 처음에는 모두 0이다. 다음 네 가지 연산을 사용할 수 있다.

1. modify(x): 노드 x와 x의 모든 인접 노드에 대해 각 노드의 표시를 w에서 w ⊕ 1로 바꾼다(⊕는 배타적 논리합).

2. query(x): 노드 x의 현재 w 값을 반환한다.

3. report(x,y): x와 y 사이에 간선이 있음을 기록한다.

4. check(x): x에 연결된 모든 간선이 보고되었는지 확인한다.

각 연산은 각각 Lm, Lq, M, Lc번까지 사용할 수 있다.

구현해야 하는 함수는 explore(N,M)이다. N과 M은 각각 노드 수와 간선 수를 나타낸다.

헤더 explore.h를 포함하면 다음 네 함수를 호출할 수 있다.

1. modify(x): 반환값이 없다. 0 ≤ x < N을 만족해야 한다.

2. query(x): 노드 x의 w 값을 반환한다. 0 ≤ x < N을 만족해야 한다.

3. report(x,y): 노드 x와 y 사이의 간선을 기록한다. 0 ≤ x, y < N, x ≠ y를 만족해야 한다.

4. check(x): 노드 x의 상태를 반환한다. 0 ≤ x < N을 만족해야 한다. x에 연결된 모든 간선이 기록되었으면 1, 그렇지 않으면 0을 반환한다.

모든 그래프는 미리 고정되어 있으며 바뀌지 않는다.

N의 일의 자리 숫자를 보고 특수한 그래프와 그 밖의 경우를 구분할 수 있다.