백준(BOJ) 2316 도시 왕복하기 ***

# 네트워크 플로우 # 최대 유량

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef struct st
{
    int from;
    int to;
    vector<int> pre;
}ho;
int n,m,a,b,st=1,fi=2,use[405][405],ans=0;
bool tf=true;
vector<int> v[405];
queue<ho> q;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    vector<int> new1;
    new1.push_back(1);
    
    while(tf)
    {
        bool visit[405]={0,};
        visit[1]=true;
        ho tmp={0,1,new1};
        while(!q.empty())
            q.pop();
        q.push(tmp);
        tf=false;
        
        while(!q.empty())
        {
            ho tmp= q.front();
            q.pop();
            if(tmp.to==2)
            {
                if(tmp.from==1)
                    continue;
                tmp.pre.push_back(2);
                for(int i=0;i<tmp.pre.size()-1;i++)
                    use[tmp.pre[i]][tmp.pre[i+1]]=1;
                
                bool dd=false;
                for(int i=0;i<tmp.pre.size()-2;i++)
                {
                    int zero=0;
                    for(int k=1;k<=n;k++)
                        if(use[k][tmp.pre[i+1]]==1&&use[tmp.pre[i+1]][k]==0)
                            zero++;
                    if(zero>1)
                    {
                        dd=true;
                        break;
                    }
                }
                if(dd)
                {
                    for(int i=0;i<tmp.pre.size()-1;i++)
                        use[tmp.pre[i]][tmp.pre[i+1]]=0;
                    continue;
                }
                ans++;
                tf=true;
                break;
            }
            for(int i=0;i<v[tmp.to].size();i++)
            {
                if(visit[v[tmp.to][i]]==false&&use[tmp.to][v[tmp.to][i]]==0)
                {
                    vector<int> new2 =tmp.pre;
                    if(v[tmp.to][i]!=2)
                    {
                        visit[v[tmp.to][i]]=true;
                        new2.push_back(v[tmp.to][i]);
                    }
                    ho next={tmp.to,v[tmp.to][i],new2};
                    q.push(next);
                }
            }
        }
    }
    printf("%d",ans);
}
    return 0;