MakeBipartite

Sile a învățat la ora de matematică definiția unui graf bipartit. Considerăm un graf neorientat $G$ format dintr-o mulțime de noduri $V$ și o mulțime de muchii $E$. Spunem că $G$ este bipartit dacă și numai dacă există două submulțimi $V^1, V^2 \subseteq V$ astfel încât:

• $V^1 \cap V^2 = \varnothing$;
• $V^1 \cup V^2 = V$;
• fiecare muchie din $E$ are o extremitate în $V^1$ și o extremitate în $V^2$.

Sile a dat peste un graf neorientat $G$, cu nodurile $V$ și muchiile $E$, format din $N$ noduri ($V = \{1, 2, \dots, N\}$) și $M$ muchii ($|E| = M$). El se întreabă acum pentru care noduri $v \in V$ avem că graful $G \setminus v$ obținut prin eliminarea nodului $v$ și a muchiilor incidente lui $v$ din $G$ este bipartit.

Voi va trebui să îl ajutați pe Sile să își rezolve problema pentru $T$ scenarii.

Protocol de interacțiune

Concurentul trebuie să implementeze următoarea funcție, care va fi apelată pentru $T$ scenarii independente:

void solve(int N, int M, int* X, int* Y, char* S);

$N$ reprezintă numărul de noduri ale grafului, $M$ numărul de muchii ale grafului. $X$ și $Y$ sunt două șiruri de lungime $M$ ce codifică mulțimea de muchii a grafului: pentru fiecare $0 \leq i < M$ există o muchie între $X_i$ și $Y_i$. Concurentul trebuie să scrie răspunsul în șirul $S$ de lungime $N$: pentru $0 \leq i < N$ vom avea că $S_i =$ 1 dacă graful $G \setminus \{i+1\}$ este bipartit, și $S_i =$ 0 altfel. Valorile scrise în $S$ sunt caractere, nu numere.

Restricții

• Nu vor exista muchii cu $a = b$.
• Nu vor exista muchii care să apară de mai multe ori în cadrul aceluiași scenariu.
• Se consideră identice muchiile $(a, b)$ și $(b, a)$.

Subtask 1 (23 puncte)

• $1 \leq T \leq 600$
• $1 \leq N \leq 2\ 000$
• $1 \leq M \leq 5\ 000$
• Suma valorilor $N$ nu va depăși $20\ 000$.
• Suma valorilor $M$ nu va depăși $20\ 000$.

Subtask 2 (32 puncte)

• $1 \leq T \leq 20\ 000$
• $1 \leq N \leq 100\ 000$
• $1 \leq M \leq 250\ 000$
• Suma valorilor $N$ nu va depăși $120\ 000$.
• Suma valorilor $M$ nu va depăși $350\ 000$.
• Se acordă punctaj complet oricărei surse care găsește răspunsul corect cel puțin pentru nodurile $v \in V$ pentru care există maxim două muchii incidente în $G$. Cu toate acestea, se cere ca valorile $S_i$ să fie mereu 0 sau 1 pentru $0 \leq i < N$.

Subtask 3 (22 puncte)

• $1 \leq T \leq 20\ 000$
• $1 \leq N \leq 100\ 000$
• $1 \leq M \leq 250\ 000$
• Suma valorilor $N$ nu va depăși $120\ 000$.
• Suma valorilor $M$ nu va depăși $350\ 000$.

Subtask 4 (23 puncte)

• $1 \leq T \leq 40\ 000$
• $1 \leq N \leq 1\ 000\ 000$
• $1 \leq M \leq 2\ 500\ 000$
• Suma valorilor $N$ nu va depăși $1\ 000\ 000$.
• Suma valorilor $M$ nu va depăși $2\ 500\ 000$.

Exemplu

Explicație

Avem $T = 2$ scenarii de rezolvat.

În primul scenariu graful $G$ este cel din imaginea de mai jos.

Observăm că nodurile $1$, $2$ și $3$ sunt vecine două câte două, de unde deducem că graful $G$ nu este bipartit. Prin eliminarea oricăruia dintre nodurile $1$, $2$ sau $3$, graful rezultat va fi bipartit. De exemplu, dacă am elimina nodul $2$ (implicit și muchiile sale incidente $2 – 1$ și $2 – 3$), atunci graful rezultat $G \setminus \{2\}$ va fi bipartit, deoarece se pot alege submulțimile $V^1 = \{1, 4\}$ și $V^2 = \{3\}$ respectând proprietățile din enunț (n.b. există și alte modalități de a alege mulțimile $V^1$, $V^2$). Eliminarea nodului $4$ nu ar duce la un graf bipartit. Așadar, răspunsul pentru acest scenariu este 1110.

În al doilea scenariu graful $G$ este cel din imaginea de mai jos.

În acest caz, indiferent ce nod $v \in V$ s-ar elimina din $G$, graful rezultat $G \setminus \{v\}$ nu ar fi bipartit. Așadar, răspunsul în acest caz este 000000.