비

최근 몇 년 동안 허리케인과 쓰나미는 물의 파괴력을 보여 주었다. 그 힘은 바다에만 머물지 않는다. 폭우는 홍수를 일으켜 집과 농지를 망가뜨릴 수 있다. 과학자들은 정교한 모델을 사용해 큰비가 내렸을 때 물이 어디에 고일지 예측한다.

언덕이 많은 지형은 삼각분할로 모델링할 수 있다. 삼각분할은 삼각형으로 곡면을 근사하는 방법이다. 삼각형의 변은 인접한 두 삼각형이 함께 공유한다. 다만 영역의 경계에 있는 삼각형은 공유되지 않는 변을 가질 수 있다.

지형의 삼각분할 모델이 주어졌다고 하자. 비가 쏟아지면 일부 물은 바다로 흘러가고, 나머지는 지형에 갇혀 호수를 이룬다. 이때 생기는 호수의 개수와 각 호수의 수위를 구하라. 비는 모든 호수를 최대 수위까지 채울 만큼 충분히 내린다고 가정한다.

호수의 수면 위에서 경계를 제외한 두 점 사이는 아무리 작아도 0이 아닌 크기의 배로 항해할 수 있다. 따라서 깊이가 0인 점만 공유하는 두 호수는 서로 다른 호수이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 점의 개수 $p \ge 3$과 변의 개수 $s \ge 3$이 주어진다. 이어지는 $p$개의 줄은 각각 점을 설명한다. 각 줄은 테스트 케이스 안에서 유일한 두 글자 코드로 시작하고, 그 뒤에 정수 $x$, $y$, $h$가 차례로 주어진다. 여기서 $-10000 \le x, y \le 10000$은 평면 좌표이고, $0 \le h \le 8848$은 해수면 위의 높이이다.

이어지는 $s$개의 줄은 변 하나를 설명한다. 변은 서로 다른 두 글자 코드로 된 두 끝점으로 주어진다. 변을 xy 평면에 투영한 결과는 다음 조건을 만족한다.

• 어떤 변도 자신의 끝점 이외의 곳에서 다른 변과 교차하지 않는다.
• 점과 변은 하나의 연결된 영역을 이루는 삼각분할을 만든다.
• 영역 안에 구멍이 없다. 즉 경계는 하나의 닫힌 다각선이다.

영역 밖의 점은 경계에서 가장 가까운 점보다 낮다고 본다. 따라서 물이 경계에 닿으면 자유롭게 밖으로 흘러나간다.

입력의 마지막 줄에는 0 0이 주어진다.

각 테스트 케이스마다 케이스 번호를 출력하고, 영역 안에 생기는 서로 다른 모든 호수의 수위를 한 줄에 하나씩 비내림차순으로 출력한다. 수위는 해수면 위의 높이이다. 호수가 없으면 0을 한 줄에 출력한다. 출력 형식을 정확히 따른다.