Split the Attractions

There are $n$ attractions in Baku, numbered from $0$ to $n-1$. There are also $m$ two-way roads, numbered from $0$ to $m-1$. Each road connects two different attractions. Any pair of attractions can be reached from each other through the roads.

Fatima plans to visit all of the attractions in three days. She wants to visit $a$ attractions on the first day, $b$ on the second day, and $c$ on the third day. She will partition the $n$ attractions into three sets $A$, $B$, and $C$ of sizes $a$, $b$, and $c$. Each attraction belongs to exactly one set, so $a + b + c = n$.

A set $S$ of attractions is connected if any two attractions in $S$ can reach each other by roads without passing through an attraction outside $S$. Find sets $A$, $B$, and $C$ so that at least two of the three sets are connected. A partition that meets this condition is valid.

Given $a$, $b$, and $c$, find a valid partition, or determine that no valid partition exists. If several valid partitions exist, you may output any of them.

• $3 \leq n \leq 100\,000$
• $2 \leq m \leq 200\,000$
• $1 \leq a, b, c \leq n$
• $a+b+c = n$
• There is at most one road between each pair of attractions.
• Any pair of attractions can be reached from each other through the roads.
• $0 \leq p[i], q[i] \leq n-1$ and $p[i] \neq q[i]$ for $0 \leq i \leq m - 1$