1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <map>
#include <bits/stdc++.h>
using namespace std;

void buildEdges(vector<int>& parent, int s, int d, vector<vector<int> >& adjList)
{
vector<int> path;
  while (s != d)
  {
     if (find( adjList[d].begin(),  adjList[d].end(),s)== adjList[d].end()) 
     {
    path.push_back(s+1); path.push_back(d+1);
    adjList[d].push_back(s);
    adjList[s].push_back(d);}
      d = parent[d];
  }
  for(int i=0;i<path.size()/2;++i)  cout << "+ "<< path[path.size()-2*i-1] << " " << path[path.size()-2*i-2] <<endl;
  for(int i=1;i<path.size()/2;++i)  cout << "- "<< path[2*i] << " " << path[2*i+1] <<endl;

}

void bfs(vector<vector<int> >& adjList, int source, int dest, int n)
{
    vector<int> parent(n, 0);
    vector<int> path(n, 0);

    int front = -1, back = -1;
    vector<int> visited(n, 0);

    path[++back] = source;
    int k;

    while (front != back)
    {
        k = path[++front];
        for (int j:adjList[k])
        {
            if (visited[j] == 0) 
            {
                path[++back] = j;
                visited[j] = 1;
                parent[j] = k;
            }
        }
    }
    buildEdges(parent, source, dest, adjList);
}
int main()
{
    ios_base::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    vector<vector<int> > adjList(n, vector<int>{});
    for(int i=0;i<m;++i)
    {
        int a,b; cin>>a>>b;
    adjList[a-1].push_back(b-1);
    adjList[b-1].push_back(a-1);
    }
    //zbudowany adjList
    int m2; cin>>m2;
    for(int i=0;i<m2;++i)
    {
        int a,b; cin>>a>>b;
        bfs(adjList, a-1,b-1, n);
    }
}