Naboj
레이팅 미적용의견: 0
Mr. Šikić, a chemistry teacher, is playing around with \(n\) metal balls and \(m\) copper wires. He joined
together some pairs of balls with a wire so that all the balls are (directly or indirectly) linked to each
other. He wants to teach his students about electric charge so he’ll demonstrate it by charging the metal
balls in a sequence.
Mr Šikić can either charge each of the balls positively or negatively. When a ball is charged negatively,
the electrons in all the wires connected to the ball are repulsed to the other ball connected to that wire.
Conversely, if a ball is positively charged, the electrons from all the wires connected to that ball are pulled
towards it. Charging the balls has the same effect on the wires irrespective of the wire’s previous state.
At the beginning of the class all the balls hold no charge and the electrons in all the wires are still. For
every wire Mr. Šikić has a specific direction of the electron flow in mind. Help him find a sequence of ball
chargings that results in the desired electron flows.
Subtask 1 (15 points): \(1 \le n \le 10\)
Subtask 2 (25 points): \(m = n - 1\)
Subtask 3 (70 points): No additional constraints.
The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 200\,000\), \(1 \le m \le 500\,000\)) from the task statement.
The following \(m\) lines contain integers \(a_{i}\) and \(b_{i}\) (\(1 \le a_{i}\), \(b_{i} \le n\), \(a_{i}\)̸ = \(b_{i}\)) denoting that the balls \(a_{i}\) and \(b_{i}\)
are connected by a wire and the electrons in the wire should be closer to \(a@@RISE_MATH_BLOCK_0@@i\). There is at most
one wire between a pair of balls. All the balls are directly or indirectly connected by wires.
If it is impossible to direct the flow of electrons according to Mr. Šikić’s wishes pri\(nt -1\). Otherwise print
\(k\), the required number of ball chargings. \(k\) must be less than or equal 200 000.
In the following \(k\) lines print integers \(c@@RISE_MATH_BLOCK_0@@i\) (\(1 \le c@@RISE_MATH_BLOCK_1@@i \le 1\)), the number of the ball Mr. Šikić
should charge in \(i-th\) step and whether it should be charged positively (denoted by \(d\)\(i = 1\)) or negatively
(\(d_{i} = 0\)). If there are multiple solutions, print any one of them.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | \(1 \le n \le 10\) |
2 | 25점 | \(m = n - 1\) |
3 | 70점 | No additional constraints. |
3 3
1 2
2 3
1 33
2 1
3 0
1 14 3
1 2
3 2
2 44
2 1
4 0
3 1
1 15 10
2 4
3 4
1 4
4 5
3 2
2 1
5 2
1 3
5 3
1 5-1Clarification of the first example:
First, we give the ball 2 a positive charge. The electrons on wires between balls 1 and 2, and balls 2 and 3
are now closer to the ball 2. The wire connecting balls 1 and 3 remains neutral.
Now we give ball 3 a negative change. The arrangement of electrons between wires 2 and 3 remains
unchanged, while the electrons on the wire between 1 and 3 are closer to the ball 1.
Finally we give ball 1 a positive charge. The wire between 1 and 3 remains unchanged, but on the wire
between balls 1 i 2 electrons are now closer to the ball 1 and the desired arrangement is achieved.
평가 및 의견
Naboj
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Naboj