haison3000
28-02-2003, 12:39
PROBLEM 4: Traveling Cows [Brian Dean, 1999]
N (3 <= N <= 400) fields numbered 1..N are connected by P (1 <= P <=
10,000) bidirectional pathways. Fields 1 and 2 contain barns. Bessie
wants to travel on the paths back and forth between these two barns as
many times as possible -- however, she doesn't want to visit any field
more than one time in all her trips (except for the fields containing
barns). Bessie must visit at least one non-barn field when traveling
between the two barns; the input set contains neither "1 2" nor "2 1".
What is the maximum number of trips Bessie can make?
INPUT FORMAT:
* Line 1: Two integers: N and P
* Lines 2..P+1: Two integers that represent two fields connected by a
path
SAMPLE INPUT (file barn.in):
7 10
1 3
1 5
1 6
2 4
2 5
2 7
3 4
3 5
5 7
6 7
OUTPUT FORMAT:
A single integer that is the maximum number of trips that Bessie can
make.
SAMPLE OUTPUT (file barn.out):
3
BÀi này đệ từng giải wa nhưng wên mất rồi.
N (3 <= N <= 400) fields numbered 1..N are connected by P (1 <= P <=
10,000) bidirectional pathways. Fields 1 and 2 contain barns. Bessie
wants to travel on the paths back and forth between these two barns as
many times as possible -- however, she doesn't want to visit any field
more than one time in all her trips (except for the fields containing
barns). Bessie must visit at least one non-barn field when traveling
between the two barns; the input set contains neither "1 2" nor "2 1".
What is the maximum number of trips Bessie can make?
INPUT FORMAT:
* Line 1: Two integers: N and P
* Lines 2..P+1: Two integers that represent two fields connected by a
path
SAMPLE INPUT (file barn.in):
7 10
1 3
1 5
1 6
2 4
2 5
2 7
3 4
3 5
5 7
6 7
OUTPUT FORMAT:
A single integer that is the maximum number of trips that Bessie can
make.
SAMPLE OUTPUT (file barn.out):
3
BÀi này đệ từng giải wa nhưng wên mất rồi.