SPOJ.com - Problem BCCOLOR

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCCOLOR - Tô màu kì quặc

Cho đồ thị vô hướng G . Bạn cần phải tô màu các cạnh của G bằng các màu 0,1,2 sao cho:

Tổng của các màu của tất cả các cạnh là nhỏ nhất.

Với mỗi cạnh có màu 0 , phải có 1 cạnh kề sao cho màu của cạnh đó là 2. Hai cạnh kề nhau nếu chúng có 1 đỉnh chung.

Input

Dòng đầu chứa số bộ test.

Mỗi test, dòng đầu chứa 2 số n,m ( 1≤n≤20 và 1≤m≤30), tương ứng là số đỉnh và số cạnh. Sau đó là m dòng, mỗi dòng là 2 đỉnh của cạnh.

Output

Với mỗi test, xuất ra tổng các cạnh bé nhất thỏa mãn .

English Version:

You are given an undirected graph G . You should paint the edges of G with colors 0,1,2 such that:

Sum of colors of all edges be minimum.

For each edge with color 0, there must be an adjacent edge such that the color of that edge is 2. Two edges are adjacent if they have a common vertex.

Input

First line of Input contains the number of the tests.

For each case, first you are given ( 1≤n≤20 và 1≤m≤30) ,the number of vertices and edges respectively. In the following m lines, in each line you are given two endpoints of an edge.

Output

For each case, output minimum number of sum of the edges that have appropriate properties.

Sample Input

Sample Output

3 3

1 2

2 3

1 3

18 27

1 2

1 4

1 6

3 2

3 4

3 6

2 5

4 5

7 8

7 10

7 12

9 8

9 10

9 12

8 11

10 11

13 14

13 16

13 18

15 14

15 16

15 18

14 17

16 17

5 11

12 17

18 6

ID	RESULT	TIME

code...

Submit solution!

Được gửi lên bởi:	adm
Ngày:	2011-10-31
Thời gian chạy:	1s-10s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Nguồn bài:	Tehran IC10

hide comments



2019-07-16 00:54:29 vì nó khó :v
2014-11-22 19:36:08 Long Hoàng sao ghi dòng đầu 2 số mà có 1 số v ad ơi :(
2014-09-22 18:37:34 Hồ Vãn Anh - ÐHKHTN sao bài này chả có ma nào thèm làm thế

Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

BCCOLOR - Tô màu kì quặc

Input

Output

English Version:

Input

Output