// 다이어그램. 화살표로 적은 방향 그래프를 위상 정렬해 최장 경로 기준으로 층을 나누고 SVG 로 그립니다.
// 입력은 줄마다 `A -> B -> C` 같은 간선 사슬이고 노드 하나만 적은 줄은 독립 노드입니다. 노드 이름에는 공백과 붙임표를 쓸 수 없습니다.
// 출력은 SVG 를 담은 HTML 조각이고, 순환이 있으면 순환에 속한 노드를 첫 등장 순으로 적은 오류 조각입니다.
// 같은 입력이면 인터프리터와 웹 빌드에서 바이트까지 같은 출력을 냅니다.
// 무방향 그래프, 힘 기반 배치, 곡선 연결선, 첫 등장 순서를 넘는 교차 줄이기는 하지 않습니다.
// Diagram: layers a directed graph by longest path and renders it as SVG.

record 그래프 { 노드들: Array<string>, 간선들: Array<간선> }
record 선분 { 출발: int, 도착: int, 화살촉: bool }
record 층배치 { 층들: Array<int>, 행들: Array<int>, 선분들: Array<선분>, 층수: int, 행수: int }

let 빈입력안내 = "<div class=\"meta\">그래프를 입력하세요. 예: A -> B -> C</div>"
let 화살촉표시 = " marker-end=\"url(#arrow)\""

// 공용 도우미 시작 (이스케이프 오류알림 간선 위상정렬결과 인접목록 위상정렬하기 순환소속인가 결과풀기)
// 여러 도구가 같은 원본을 씁니다. 여기서 고치지 않고 원본에서 고친 뒤 다시 생성합니다.

// 사용자 입력을 HTML 에 넣기 전에 반드시 거칩니다.
function 이스케이프(원문: string) -> string {
  원문.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;").replace("\"", "&quot;")
}

// 문구는 고정 문장이거나 이미 이스케이프한 값이어야 합니다.
function 오류알림(문구: string) -> string {
  "<div class=\"err\">{문구}</div>"
}

type 간선 = { 출발: int, 도착: int }

// 순서는 Kahn 대기열 순서, 층은 최장 경로 길이입니다. 남은 진입차수가 0 보다 큰 노드는 순환 때문에 놓지 못한 노드입니다.
type 위상정렬결과 = { 순서: Array<int>, 층들: Array<int>, 남은진입차수: Array<int> }

// 한 번 만들어 두면 위상 정렬과 순환 검사가 노드마다 간선 전체를 다시 훑지 않습니다. 행 안의 순서는 간선 순서입니다.
function 인접목록(노드수: int, 간선들: Array<간선>) -> Array<Array<int>> {
  let mut 인접: Array<Array<int>> = [for i in 0..<노드수 => []]
  for 연결 in 간선들 { 인접[연결.출발].push(연결.도착) }
  인접
}

function 위상정렬하기(인접: Array<Array<int>>) -> 위상정렬결과 {
  let n = 인접.length
  let mut 진입차수 = [for i in 0..<n => 0]
  for 도착들 in 인접 {
    for 도착 in 도착들 { 진입차수[도착] += 1 }
  }
  let mut 층들 = [for i in 0..<n => 0]
  let mut 대기열 = [for i in 0..<n if 진입차수[i] == 0 => i]
  let mut 머리 = 0
  while 머리 < 대기열.length {
    let 현재 = 대기열[머리]
    머리 += 1
    for 도착 in 인접[현재] {
      진입차수[도착] -= 1
      층들[도착] = 층들[도착].atLeast(층들[현재] + 1)
      if 진입차수[도착] == 0 { 대기열.push(도착) }
    }
  }
  { 순서: 대기열, 층들: 층들, 남은진입차수: 진입차수 }
}

// 순환을 가리키기만 하는 노드도 위상 정렬에서 남으므로 길이 1 이상의 경로로 자기 자신에게 돌아오는지 따로 봅니다.
function 순환소속인가(시작: int, 인접: Array<Array<int>>) -> bool {
  let mut 방문: Set<int> = Set.of()
  // 인접 목록의 행에 직접 넣지 않도록 복사해서 시작합니다.
  let mut 대기열 = 인접[시작].slice(0, 인접[시작].length)
  let mut 머리 = 0
  while 머리 < 대기열.length {
    let 현재 = 대기열[머리]
    머리 += 1
    if 현재 == 시작 { return true }
    if !(현재 in 방문) {
      방문.add(현재)
      for 다음 in 인접[현재] { 대기열.push(다음) }
    }
  }
  false
}

// 성공 값과 안내가 모두 바로 보여 줄 HTML 조각일 때 진입점에서 한 번 풉니다. 토파즈 과제 'Result 오류 쪽 변환과 풀기' 의 우회입니다.
function 결과풀기(값: Result<string, string>) -> string {
  match 값 {
    case Ok(결과) => 결과
    case Err(안내) => 안내
  }
}

// 공용 도우미 끝

// 공백인가와 달리 CR 은 막지 않습니다. `<`, `&`, `"` 는 이름으로 받고 그릴 때 이스케이프합니다.
function 노드이름인가(이름: string) -> bool {
  이름 != "" && 이름.scalars().filter(글자 => 글자 == " " || 글자 == "\t" || 글자 == "-").length == 0
}

// 빈 줄은 노드가 없는 사슬입니다. `->` 로 나누므로 붙여 쓴 `A->B` 와 띄어 쓴 `A -> B` 가 같습니다.
function 사슬읽기(입력줄: string, 줄번호: int) -> Result<Array<string>, string> {
  let 다듬은줄 = 입력줄.trim()
  if 다듬은줄 == "" { return Ok([]) }
  let 이름들 = 다듬은줄.split("->").map(조각 => 조각.trim())
  if 이름들.filter(이름 => !노드이름인가(이름)).length > 0 {
    return Err(오류알림("{줄번호}번째 줄: 노드 이름이 잘못되었습니다. 형식은 A -> B -> C 입니다."))
  }
  Ok(이름들)
}

// 노드 색인은 첫 등장 순서이고 층 안의 배치와 순환 보고가 이 순서를 따릅니다. 같은 간선은 한 번만 넣습니다.
// 자기 자신을 가리키는 간선도 넣어 노드 하나짜리 순환으로 알립니다.
function 그래프읽기(입력: string) -> Result<그래프, string> {
  let 줄목록 = 입력.split("\n")
  let mut 노드들: Array<string> = []
  let mut 노드색인: Map<string, int> = Map.new()
  let mut 간선들: Array<간선> = []
  let mut 넣은간선: Set<string> = Set.of()
  for 줄번호 in 0..<줄목록.length {
    let 이름들 = 사슬읽기(줄목록[줄번호], 줄번호 + 1)?
    let mut 사슬: Array<int> = []
    for 이름 in 이름들 {
      let 색인 = match 노드색인.get(이름) {
        case Some(찾음) => 찾음
        case None => {
          노드색인.insert(이름, 노드들.length)
          노드들.push(이름)
          노드들.length - 1
        }
      }
      사슬.push(색인)
    }
    for i in 1..<사슬.length {
      let 키 = "{사슬[i - 1]}->{사슬[i]}"
      if !(키 in 넣은간선) {
        넣은간선.add(키)
        간선들.push({ 출발: 사슬[i - 1], 도착: 사슬[i] })
      }
    }
  }
  Ok(그래프 { 노드들: 노드들, 간선들: 간선들 })
}

// 한 층을 넘는 간선은 중간 층마다 가상 노드를 넣어 선분이 한 층씩만 건너게 합니다. 가상 노드는 실제 노드 뒤에 색인을 받습니다.
// 층 안의 행은 색인 순이라 가상 노드는 같은 층 실제 노드들 아래 행에 놓여 박스를 비켜 갑니다.
function 배치하기(간선들: Array<간선>, 층들: Array<int>) -> 층배치 {
  let mut 노드층들 = 층들.slice(0, 층들.length)
  let mut 선분들: Array<선분> = []
  for 연결 in 간선들 {
    let mut 앞 = 연결.출발
    for 중간층 in (층들[연결.출발] + 1)..<층들[연결.도착] {
      노드층들.push(중간층)
      선분들.push(선분 { 출발: 앞, 도착: 노드층들.length - 1, 화살촉: false })
      앞 = 노드층들.length - 1
    }
    선분들.push(선분 { 출발: 앞, 도착: 연결.도착, 화살촉: true })
  }
  let 층수 = 노드층들.reduce(0, (최대, 층) => 최대.atLeast(층)) + 1
  let mut 층별개수 = [for i in 0..<층수 => 0]
  let mut 행들: Array<int> = []
  for 노드층 in 노드층들 {
    행들.push(층별개수[노드층])
    층별개수[노드층] += 1
  }
  층배치 {
    층들: 노드층들,
    행들: 행들,
    선분들: 선분들,
    층수: 층수,
    행수: 층별개수.reduce(0, (최대, 개수) => 최대.atLeast(개수)),
  }
}

// 층마다 가로 180, 행마다 세로 70 입니다. 박스는 층 칸의 20부터 140까지라 선분은 층 사이 빈 곳에서만 그려집니다.
function 박스왼쪽(층: int) -> int {
  층 * 180 + 20
}

function 박스오른쪽(층: int) -> int {
  층 * 180 + 140
}

function 행가운데(행: int) -> int {
  행 * 70 + 40
}

function 선그리기(x1: int, y1: int, x2: int, y2: int, 끝표시: string) -> string {
  "<line x1=\"{x1}\" y1=\"{y1}\" x2=\"{x2}\" y2=\"{y2}\" stroke=\"#111\" stroke-width=\"1.5\"{끝표시}/>"
}

function 선분그리기(구간: 선분, 층들: Array<int>, 행들: Array<int>) -> string {
  let 끝표시 = if 구간.화살촉 { 화살촉표시 } else { "" }
  선그리기(박스오른쪽(층들[구간.출발]), 행가운데(행들[구간.출발]), 박스왼쪽(층들[구간.도착]), 행가운데(행들[구간.도착]), 끝표시)
}

function 상자그리기(이름: string, x: int, y: int) -> string {
  [
    "<rect x=\"{x}\" y=\"{y}\" width=\"120\" height=\"40\" fill=\"#fff\" stroke=\"#111\"/>",
    "<text x=\"{x + 60}\" y=\"{y + 25}\" text-anchor=\"middle\" font-family=\"ui-monospace, monospace\" font-size=\"13\" fill=\"#111\">{이스케이프(이름)}</text>",
  ].join("")
}

function 그리기(노드들: Array<string>, 배치: 층배치) -> string {
  let 층들 = 배치.층들
  let 행들 = 배치.행들
  let 연결선들 = 배치.선분들.map(구간 => 선분그리기(구간, 층들, 행들))
  // 가상 노드는 자기 층의 박스 띠를 가로지르는 선으로 들어온 선분과 나가는 선분을 잇습니다.
  let 이음선들 = [for i in 노드들.length..<층들.length => 선그리기(박스왼쪽(층들[i]), 행가운데(행들[i]), 박스오른쪽(층들[i]), 행가운데(행들[i]), "")]
  let 상자들 = [for i in 0..<노드들.length => 상자그리기(노드들[i], 박스왼쪽(층들[i]), 행들[i] * 70 + 20)]
  let 폭 = 배치.층수 * 180 + 40
  let 높이 = 배치.행수 * 70 + 40
  let 조각들 = [
    "<svg class=\"diagram\" viewBox=\"0 0 {폭} {높이}\" width=\"{폭}\" height=\"{높이}\" xmlns=\"http://www.w3.org/2000/svg\">",
    "<defs><marker id=\"arrow\" markerWidth=\"9\" markerHeight=\"9\" refX=\"8\" refY=\"3\" orient=\"auto\"><path d=\"M0,0 L8,3 L0,6 Z\" fill=\"#111\"/></marker></defs>",
    연결선들.join(""),
    이음선들.join(""),
    상자들.join(""),
    "</svg>",
  ]
  "<div class=\"out\">" + 조각들.join("") + "</div>"
}

function 다이어그램(입력: string) -> Result<string, string> {
  let 입력그래프 = 그래프읽기(입력)?
  if 입력그래프.노드들.length == 0 { return Err(빈입력안내) }
  let 인접 = 인접목록(입력그래프.노드들.length, 입력그래프.간선들)
  let 정렬결과 = 위상정렬하기(인접)
  let 못놓은노드들 = [for i in 0..<인접.length if 정렬결과.남은진입차수[i] > 0 => i]
  if 못놓은노드들.length > 0 {
    let 순환노드들 = 못놓은노드들.filter(노드 => 순환소속인가(노드, 인접)).map(노드 => 이스케이프(입력그래프.노드들[노드]))
    return Err(오류알림("순환이 있어 배치할 수 없습니다: {순환노드들.join(", ")}"))
  }
  Ok(그리기(입력그래프.노드들, 배치하기(입력그래프.간선들, 정렬결과.층들)))
}

input() |> 다이어그램 |> 결과풀기 |> print