codeforces-scrape

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

505B.md (2278B)


      1 Source: https://codeforces.com/problemset/problem/505/B
      2 
      3 B. Mr. Kitayuta's Colorful Graph
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Mr. Kitayuta has just bought an undirected graph consisting of *n* vertices and *m* edges. The vertices of the graph are numbered from 1 to *n*. Each edge, namely edge *i*, has a color *c**i*, connecting vertex *a**i* and *b**i*.
     22 
     23 Mr. Kitayuta wants you to process the following *q* queries.
     24 
     25 In the *i*-th query, he gives you two integers — *u**i* and *v**i*.
     26 
     27 Find the number of the colors that satisfy the following condition: the edges of that color connect vertex *u**i* and vertex *v**i* directly or indirectly.
     28 
     29 Input
     30 
     31 The first line of the input contains space-separated two integers — *n* and *m* (2 ≤ *n* ≤ 100, 1 ≤ *m* ≤ 100), denoting the number of the vertices and the number of the edges, respectively.
     32 
     33 The next *m* lines contain space-separated three integers — *a**i*, *b**i* (1 ≤ *a**i* < *b**i* ≤ *n*) and *c**i* (1 ≤ *c**i* ≤ *m*). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if *i* ≠ *j*, (*a**i*, *b**i*, *c**i*) ≠ (*a**j*, *b**j*, *c**j*).
     34 
     35 The next line contains a integer — *q* (1 ≤ *q* ≤ 100), denoting the number of the queries.
     36 
     37 Then follows *q* lines, containing space-separated two integers — *u**i* and *v**i* (1 ≤ *u**i*, *v**i* ≤ *n*). It is guaranteed that *u**i* ≠ *v**i*.
     38 
     39 Output
     40 
     41 For each query, print the answer in a separate line.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 4 5  
     49 1 2 1  
     50 1 2 2  
     51 2 3 1  
     52 2 3 3  
     53 2 4 3  
     54 3  
     55 1 2  
     56 3 4  
     57 1 4
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 2  
     64 1  
     65 0
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 5 7  
     72 1 5 1  
     73 2 5 1  
     74 3 5 1  
     75 4 5 1  
     76 1 2 2  
     77 2 3 2  
     78 3 4 2  
     79 5  
     80 1 5  
     81 5 1  
     82 2 5  
     83 1 5  
     84 1 4
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 1  
     91 1  
     92 1  
     93 1  
     94 2
     95 ```
     96 
     97 Note
     98 
     99 Let's consider the first sample.
    100 
    101  ![](https://espresso.codeforces.com/8f43ac5327ccc8fd7e1c3b3f0f085d87e9391d78.png) The figure above shows the first sample. 
    102 
    103 * Vertex 1 and vertex 2 are connected by color 1 and 2.
    104 * Vertex 3 and vertex 4 are connected by color 3.
    105 * Vertex 1 and vertex 4 are not connected by any single color.