codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1210A.md (2770B)


      1 Source: https://codeforces.com/problemset/problem/1210/A
      2 
      3 A. Anadi and Domino
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Anadi has a set of dominoes. Every domino has two parts, and each part contains some dots. For every $a$ and $b$ such that $1 \leq a \leq b \leq 6$, there is exactly one domino with $a$ dots on one half and $b$ dots on the other half. The set contains exactly $21$ dominoes. Here is an exact illustration of his set:
     22 
     23  ![](https://espresso.codeforces.com/4790b40dc3411bef1cfe229c977f50c13a82c810.png) 
     24 
     25 Also, Anadi has an undirected graph without self-loops and multiple edges. He wants to choose some dominoes and place them on the edges of this graph. He can use at most one domino of each type. Each edge can fit at most one domino. It's not necessary to place a domino on each edge of the graph.
     26 
     27 When placing a domino on an edge, he also chooses its direction. In other words, one half of any placed domino must be directed toward one of the endpoints of the edge and the other half must be directed toward the other endpoint. There's a catch: if there are multiple halves of dominoes directed toward the same vertex, each of these halves must contain the same number of dots.
     28 
     29 How many dominoes at most can Anadi place on the edges of his graph?
     30 
     31 Input
     32 
     33 The first line contains two integers $n$ and $m$ ($1 \leq n \leq 7$, $0 \leq m \leq \frac{n\cdot(n-1)}{2}$) — the number of vertices and the number of edges in the graph.
     34 
     35 The next $m$ lines contain two integers each. Integers in the $i$-th line are $a_i$ and $b_i$ ($1 \leq a, b \leq n$, $a \neq b$) and denote that there is an edge which connects vertices $a_i$ and $b_i$.
     36 
     37 The graph might be disconnected. It's however guaranteed that the graph doesn't contain any self-loops, and that there is at most one edge between any pair of vertices.
     38 
     39 Output
     40 
     41 Output one integer which denotes the maximum number of dominoes which Anadi can place on the edges of the graph.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 4 4
     49 1 2
     50 2 3
     51 3 4
     52 4 1
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 4
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 7 0
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 0
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 3 1
     77 1 3
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 1
     84 ```
     85 
     86 Input
     87 
     88 ```
     89 7 21
     90 1 2
     91 1 3
     92 1 4
     93 1 5
     94 1 6
     95 1 7
     96 2 3
     97 2 4
     98 2 5
     99 2 6
    100 2 7
    101 3 4
    102 3 5
    103 3 6
    104 3 7
    105 4 5
    106 4 6
    107 4 7
    108 5 6
    109 5 7
    110 6 7
    111 ```
    112 
    113 Output
    114 
    115 ```
    116 16
    117 ```
    118 
    119 Note
    120 
    121 Here is an illustration of Anadi's graph from the first sample test:
    122 
    123  ![](https://espresso.codeforces.com/7207b245dddd41f01e13bff7ae06a57ab00b811a.png) 
    124 
    125 And here is one of the ways to place a domino on each of its edges:
    126 
    127  ![](https://espresso.codeforces.com/a6fd22079062b3e46464fd72fd2e37fa6b28db55.png) 
    128 
    129 Note that each vertex is faced by the halves of dominoes with the same number of dots. For instance, all halves directed toward vertex $1$ have three dots.