Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu proprietatea că ambele extremități au aceeași paritate. Să se determine câte muchii va avea graful parțial obținut.

Date de intrare

Fişierul de intrare graf_partial.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire graf_partial.out va conţine pe prima linie numărul M de muchii ale grafului parțial obținut.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplu

graf_partial.in

5
1 4
3 5
2 3
2 1
4 2
3 2
1 3

graf_partial.out

3

Explicație

Se elimină muchiile (3 5), (4 2), (1 3). Graful parțial obținut va avea muchiile (1 4), (2 3) și (2 1).

SOLUTIE

#include<fstream>
using namespace std;
ifstream cin("graf_partial.in");
ofstream cout("graf_partial.out");

int n,a[101][101];

void citire()
{
    cin>>n;
    
    int x,y;
    while(cin>>x && cin>>y)
    {
        a[x][y] = 1;
        a[y][x] = 1;
    }
}
int muchii = 0;

int main()
{
    citire();
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            {
                if((a[i][j] || a[j][i]) && i % 2 == j % 2)
                    a[i][j] = 0,a[j][i] = 0;
            }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(a[i][j]){
                muchii++;
            }
    }
    
    cout<<muchii/2<<'\n';
    
    
}