結果

問題 No.2403 "Eight" Bridges of Königsberg
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:40:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,146 bytes
コンパイル時間 336 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 81,664 KB
最終ジャッジ日時 2025-06-12 19:40:24
合計ジャッジ時間 4,531 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    from collections import defaultdict

    n, m = map(int, sys.stdin.readline().split())
    out_degree = defaultdict(int)
    in_degree = defaultdict(int)
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        out_degree[u] += 1
        in_degree[v] += 1

    delta = defaultdict(int)
    for u in out_degree:
        delta[u] += out_degree[u]
    for u in in_degree:
        delta[u] -= in_degree[u]

    total = sum(delta.values())
    if total != 0:
        print(-1)
        return

    S = sum(abs(d) for d in delta.values())

    if S == 0:
        print(0)
        return

    if S == 2:
        cnt_plus = 0
        cnt_minus = 0
        for d in delta.values():
            if d == 1:
                cnt_plus +=1
            elif d == -1:
                cnt_minus +=1
            elif d !=0:
                break
        else:
            if cnt_plus ==1 and cnt_minus ==1:
                print(0)
                return

    if S % 2 != 0:
        print(-1)
        return

    required = (S - 2) // 2
    print(required)

if __name__ == "__main__":
    main()
0