펀하우스

한 놀이공원이 넓은 $1000\text{ ft} \times 1000\text{ ft}$ 공간에 걸어서 통과하는 새로운 펀하우스를 짓고 있습니다. 공원은 이 공간에 벽을 세워 여러 개의 방으로 나눕니다. 일부 벽에는 문이 있어서 손님이 인접한 방 사이를 오갈 수 있습니다. 손님은 표시된 입구로 들어와 표시된 출구로 나가며, 자유롭게 돌아다닐 수 있습니다 — 입구에서 출구로 가는 경로는 여러 가지일 수 있습니다.

공원은 손님을 놀라게 하려고 "셰이커보드"(움직이는 바닥)를 설치하려고 합니다. 눈에 띄지 않도록, 셰이커보드는 설치되는 방 전체를 가득 채웁니다. 설계자들은 모든 손님이 방문 중 한 번쯤은 셰이커보드를 밟게 하고 싶지만, 셰이커보드는 비싸기 때문에 덮는 넓이를 최대한 줄이려고 합니다.

펀하우스 설계도가 주어질 때, 입구에서 출구로 가는 모든 가능한 경로가 셰이커보드가 놓인 방을 적어도 하나 지나도록 하기 위해 덮어야 하는 바닥 넓이의 최솟값을 구하세요.

이동 규칙: 손님은 입구 벽 바로 안쪽의 방으로 들어오고, 문을 통해서만 방과 방 사이를 이동하며, 출구 벽을 통해 나갑니다. 어떤 방에 놓인 셰이커보드는 그 방을 지나는 모든 손님이 밟게 되며, 여기에는 손님이 처음 들어오는 방과 마지막으로 나가는 방도 포함됩니다.

입력은 여러 개의 데이터 집합으로 이루어집니다. 각 데이터 집합의 첫 줄에는 벽의 개수 $n$ ($3 \le n \le 1000$)이 주어집니다. 이어지는 $n$개의 줄은 각각 벽 하나를 다음 형식으로 나타냅니다.

x1 y1 x2 y2 EXDW

여기서 $(x_1, y_1)$과 $(x_2, y_2)$는 벽의 양 끝점이고, 마지막 항목은 한 개의 대문자입니다.

• E — 입구;
• X — 출구;
• D — 문이 있는 내부 벽;
• W — 문이 없는 벽.

E와 X는 외벽에만 나타나고, D는 내부 벽에만 나타나며, W는 어느 쪽에도 나타날 수 있습니다. 모든 좌표는 $0$ 이상 $1000$ 이하의 정수입니다. 벽들은 끝점을 공유하는 경우를 제외하고는 서로 닿지 않으며, 모든 끝점은 다른 벽의 끝점과 정확히 겹칩니다. 길이가 $0$인 벽은 없습니다. 모든 입구는 어떤 출구로 가는 경로가 적어도 하나 있고, 모든 출구는 어떤 입구에서 오는 경로가 적어도 하나 있습니다. 펀하우스는 하나로 연결된 건물이며, 모든 내부 벽은 직접 또는 다른 벽들을 거쳐 외벽과 연결되어 있습니다.

입력의 끝은 0 하나만 있는 줄로 표시됩니다.

각 데이터 집합마다, 모든 손님이 셰이커보드를 밟도록 덮어야 하는 바닥 넓이의 최솟값을 한 줄에 출력합니다. 값은 소수점 아래 한 자리까지 정확히 출력하고, 불필요한 공백이나 답 사이의 빈 줄은 넣지 않습니다.