분자

분자는 화학 결합으로 서로 붙어 있는 원자들로 이루어진다. 각 결합은 두 원자를 연결한다. 각 원자는 여러 다른 원자와 결합할 수 있으며, 이때 각각 별개의 화학 결합으로 연결된다. 분자 안의 모든 원자는 화학 결합을 통해 직접 또는 간접적으로 서로 연결되어 있다.

분자의 화학적 성질은 원자 쌍이 화학 결합으로 어떻게 연결되어 있는지뿐만 아니라 분자 안에서 원자가 차지하는 물리적 위치에 따라서도 결정된다. 화학 결합은 원자들을 서로 끌어당길 수 있기 때문에, 분자 안 모든 화학 결합의 복잡한 상호작용을 고려하면 원자의 위치를 결정하기 어려울 때가 있다.

분자의 정보가 주어진다. 각 화학 결합은 서로 다른 두 원자를 연결하고, 각 원자 쌍 사이에는 결합이 최대 하나만 존재한다. 일부 원자의 좌표는 알려져 있고 고정되어 있으며, 나머지 원자는 각 원자가 화학 결합으로 연결된 이웃 원자들의 위치 평균이 되는 위치로 자연스럽게 움직인다. 단순화를 위해 분자 안의 원자들은 직교 좌표평면 위에 있다.

입력의 첫 번째 줄에는 두 정수 n (2 ≤ n ≤ 100)과 m (n − 1 ≤ m ≤ n(n−1)/2)이 주어진다. n은 원자의 수, m은 화학 결합의 수이다.

다음 n개 줄은 원자의 위치를 나타낸다. i번째 줄에는 두 정수 x, y (0 ≤ x, y ≤ 1 000 또는 x = y = −1)가 주어지며, 각각 i번째 원자의 x, y 좌표이다. 두 좌표가 모두 −1이면 이 원자의 위치는 알려지지 않았다.

다음 m개 줄은 화학 결합을 나타낸다. i번째 줄에는 두 정수 a와 b (1 ≤ a < b ≤ n)가 주어지며, 원자 a와 원자 b 사이에 화학 결합이 있음을 뜻한다.

위치가 고정된 원자가 최소 하나 존재한다.

각 원자의 최종 위치를 나타내는 n개 줄을 출력한다. 구체적으로, i번째 줄에는 i번째 원자의 최종 좌표인 두 수 x와 y를 출력한다. 가능한 답이 여러 개라면 그중 아무거나 출력해도 된다. 각 미지의 원자 좌표와 그 원자에 화학 결합으로 연결된 모든 이웃 원자 좌표의 평균이 10−3 이하로 차이 나면 정답으로 인정된다. 여러 원자가 같은 좌표를 가져도 된다.