solution: /submissions/accepted/niklas.py
version: 2025-08

data:
  sample:
    data:
      - '':
         in: |
           5 6
           1 2
           2 3
           3 4
           4 5
           2 4
           3 5
         ans: |
           possible
      - '':
         in: |
           2 1
           1 2
         ans: |
           impossible
      - '':
         in: |
           6 7
           1 2
           1 3
           2 6
           3 6
           2 4
           4 5
           5 6
         ans: |
           impossible
      - '':
         in: |
           6 5
           1 3
           3 6
           6 2
           2 5
           5 1
         ans: |
           possible

  secret:
    data:
      - random-small:
          generate: random --seed {seed} --n 15 --m 15
          count: 5
      - random-large:
          generate: random --seed {seed} --n 100000 --m 200000
          count: 5

      - path: path --length 99999

      - two-paths: path --length 50000 --detourStart 1 --detourEnd 50001 --detourLength 50000
      - two-paths: path --length 49999 --detourStart 1 --detourEnd 50000 --detourLength 50000
      - two-paths: path --length 49999 --detourStart 1 --detourEnd 50000 --detourLength 50001

      - path-with-detour: path --length 99998 --detourStart 1 --detourEnd 2 --detourLength 2
      - path-with-detour: path --length 99997 --detourStart 1 --detourEnd 2 --detourLength 3
      - path-with-detour: path --length 99998 --detourStart 99998 --detourEnd 99999 --detourLength 2
      - path-with-detour: path --length 99997 --detourStart 99997 --detourEnd 99998 --detourLength 3
      - path-with-detour: path --length 99998 --detourStart 12345 --detourEnd 12346 --detourLength 2
      - path-with-detour: path --length 80000 --detourStart 12345 --detourEnd 23456 --detourLength 11111
      - path-with-detour: path --length 80000 --detourStart 12345 --detourEnd 23456 --detourLength 11112

      - reversed-orientation: path --length 49999 --detourStart 1 --detourEnd 50000 --detourLength 50000 --reverseOrientation
      - reversed-orientation: path --length 99998 --detourStart 50000 --detourEnd 50001 --detourLength 2 --reverseOrientation

      - layered-small: layered --layers 5 --width 3 --branch 2 --within 0
      - layered-small: layered --layers 5 --width 3 --branch 2 --within 1
      - layered-long: layered --layers 49999 --width 2 --branch 2 --within 0
      - layered-long: layered --layers 49999 --width 2 --branch 2 --within 1
      - layered-long: layered --layers 40000 --width 2 --branch 2 --within 40000
      - layered-wide: layered --layers 10 --width 9999 --branch 2 --within 0
      - layered-wide: layered --layers 10 --width 9999 --branch 2 --within 1
      - layered-square: layered --layers 60 --width 60 --branch 50 --within 0
      - layered-square: layered --layers 60 --width 60 --branch 50 --within 10000

      - grid: grid --seed {seed} --width 316 --height 316
      - grid: grid --seed {seed} --width 316 --height 316 --diagonal
      - grid: grid --seed {seed} --width 316 --height 316 --antidiagonal
      - grid: grid --seed {seed} --width 316 --height 316 --diagonal --antidiagonal

      - triangle:
         in: |
           3 3
           1 2
           1 3
           2 3
         ans: |
           possible
      - c4:
         in: |
           4 4
           1 2
           2 3
           3 4
           4 1
         ans: |
           impossible
      - c5-possible:
         in: |
           5 5
           1 2
           2 3
           3 5
           1 4
           4 5
         ans: |
           possible
      - c5-impossible:
         in: |
           5 5
           1 2
           2 3
           3 4
           4 5
           5 1
         ans: |
           impossible
      - k4:
         in: |
           4 6
           1 2
           1 3
           1 4
           2 3
           2 4
           3 4
         ans: |
           possible
      - path3:
         in: |
           3 2
           1 2
           2 3
         ans: |
           impossible

  invalid_input:
    data:
      extra_edge:
        in: |
          4 3
          1 2
          1 3
          1 4
          2 3
      duplicate_edge:
        in: |
          4 4
          1 2
          1 3
          1 4
          4 1
      zero_based:
        in: |
          3 3
          0 1
          0 2
          1 2
      singleton:
        in: 1 0
      edgeless:
        in: |
          2 0
      loop:
        in: |
          2 2
          1 2
          2 2
      missing-st-path:
        in: |
          4 2
          1 2
          3 4
      extra-space-1:
        in: |
          3  2
          1 2
          2 3
      extra-space-2:
        in: |
          3 2
          1 2 
          2 3
      extra-newline:
        in: |
          3 2
          1 2

          2 3

  invalid_output:
    data:
  valid_output:
    data:
      upper-case:
        in: |
          3 2
          1 2
          2 3
        out: "ImpOsSibLE"
        ans: "impossible"
  invalid_answer:
    data:
      upper-case:
        in: |
          3 2
          1 2
          2 3
        ans: "Impossible"
