Go: package main

import (
    "bufio"
    "os"
    "fmt"
)

var sc = bufio.NewScanner(os.Stdin)

/**************  Cell  *****************/
type Cell struct {
    item interface{}
    next *Cell
    prev *Cell
}

func NewCell(x interface{}, ne *Cell, pr *Cell) *Cell {
    newCp := new(Cell)
    newCp.item = x
    newCp.next = ne
    newCp.prev = pr
    return newCp
}
/************  End Cell  ***************/

/**************  Queue  ****************/
type Queue struct {
    size int
    front *Cell
    rear *Cell
}

func NewQueue() *Queue {
    return new(Queue)
}

func (q *Queue) Push(x interface{}) {
    newNode := NewCell(x, nil, nil)
    if q.size == 0 {
        q.front = newNode
        q.rear = newNode
    } else {
        newNode.prev = q.rear
        q.rear.next = newNode
        q.rear = newNode
    }
    q.size++
}

func (q *Queue) PopLeft() interface{} {
    if q.size == 0 {
        return nil
    } else {
        x := q.front.item
        if q.size == 1 {
            q.front = nil
            q.rear = nil
        } else {
            q.front = q.front.next
            q.front.prev = nil
        }
        q.size--
        return x
    }
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Length() int {
    return q.size
}

type State struct {
    color string
    cnt int
}

func main() {
    for {
        sc.Scan()
        init := sc.Text()
        if init == "0" {
            break
        }
        bfs(init)
    }
}

func bfs(init string) {
    dic := make(map[string]int)
    que := NewQueue()
    que.Push(State{init, 0})
    length := len(init)
    isSolved := false
    for !que.IsEmpty() {
        state := que.PopLeft().(State)
        _, ok := dic[state.color]
        if ok {
            continue
        } else {
            dic[state.color] = state.cnt
        }

        if isSingleColor(state.color) {
            fmt.Println(state.cnt)
            isSolved = true
            break
        }

        for i := 0;i < length - 1; i++ {
            color1, color2 := string(state.color[i]), string(state.color[i + 1])
            if color1 != color2 {
                color3 := other(color1, color2)
                if i <= length - 2 {
                    que.Push(State{state.color[:i] + color3 + state.color[i + 2:], state.cnt + 1})
                } else {
                    que.Push(State{state.color[:i] + color3, state.cnt + 1})
                }
            }
        }
    }
    if !isSolved {
        fmt.Println("NA")
    }
}

func other(color1, color2 string) string {
    if color1 == "r" {
        if color2 == "g" {
            return "bb"
        } else if color2 == "b" {
            return "gg"
        }
    } else if color1 == "g" {
        if color2 == "r" {
            return "bb"
        } else if color2 == "b" {
            return "rr"
        }
    } else if color1 == "b" {
        if color2 == "r" {
            return "gg"
        } else if color2 == "g" {
            return "rr"
        }
    }
    return ""
}

func isSingleColor(color string) bool {
    for _, c := range color {
        if string(c) != string(color[0]) {
            return false
        }
    }
    return true
}

C++: #include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);

#define INF 1010000000
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

class S{
	public:
	string st;
	int n;
	S(string st,int n):st(st),n(n){}
};

int main(){
	while(1){
		string a;
		cin>>a;
		
		if(a=="0")break;
		
		queue<S> que;
		que.push(S(a,0));
		
		map<string,int> visit;
		int ans=-1;
		while(1){
			if(que.empty()==1){
				break;
			}
			
			S u=que.front();
			que.pop();
			
			if(visit[u.st]==1){
				continue;
			}
			visit[u.st]=1;
			
			int r=0,g=0,b=0;
			rep(i,u.st.size()){
				if(u.st[i]=='r'){
					r++;
				}
				if(u.st[i]=='g'){
					g++;
				}
				if(u.st[i]=='b'){
					b++;
				}
			}
			if((r==0&&g==0)||(r==0&&b==0)||(b==0&&g==0)){
				ans=u.n;
				break;
			}
			
			rep(i,u.st.size()-1){
				string nstr=u.st;
				if(u.st[i]=='r' && u.st[i+1]=='g'){
					nstr[i]=nstr[i+1]='b';
				}
				if(u.st[i]=='g' && u.st[i+1]=='r'){
					nstr[i]=nstr[i+1]='b';
				}
				if(u.st[i]=='r' && u.st[i+1]=='b'){
					nstr[i]=nstr[i+1]='g';
				}
				if(u.st[i]=='b' && u.st[i+1]=='r'){
					nstr[i]=nstr[i+1]='g';
				}
				if(u.st[i]=='b' && u.st[i+1]=='g'){
					nstr[i]=nstr[i+1]='r';
				}
				if(u.st[i]=='g' && u.st[i+1]=='b'){
					nstr[i]=nstr[i+1]='r';
				}
				
				que.push(S(nstr,u.n+1));
			}
		}
		if(ans==-1){
			puts("NA");
		}else{
			printf("%d\n",ans);
		}
	}	
}

C++: #include <iostream>
#include <string>
#include <queue>
#include <map>

using namespace std;



int main()
{
    map<string, string> ct;
    ct["rr"] = "rr";
    ct["rb"] = "gg";
    ct["rg"] = "bb";

    ct["gr"] = "bb";
    ct["gg"] = "gg";
    ct["gb"] = "rr";

    ct["br"] = "gg";
    ct["bg"] = "rr";
    ct["bb"] = "bb";

    map<string, bool> dt;
    dt["rr"] = true;
    dt["gg"] = true;
    dt["bb"] = true;
    
    for(;;) {
        string in;
        cin >> in;

        if ( in == "0" )
            break;

        std::map<string, bool> correct;
        correct[string(in.size(), 'r')] = true;
        correct[string(in.size(), 'g')] = true;
        correct[string(in.size(), 'b')] = true;

        int result_times = 0;

        queue<pair<int, string> > q;
        q.push( make_pair( 0, in ) );

        map<string, bool> memo;
        bool goal = false;

        // loop
        while( !q.empty() ) {
            int const times = q.front().first;
            string const s = q.front().second;
            q.pop();

            //cout << gtimes << endl;
            if ( correct[s] ) {
                goal = true;
                result_times = times;
                break;
            } 

            //cout << "---" << endl;
            for( size_t i=0; i<s.size()-1; ++i ){
                string const pa = s.substr( i, 2 );
                string const t = s.substr( 0, i ) + ct[pa] + s.substr( i + 2 );

                if ( t == s )
                    continue;
                if ( memo[t] )
                    continue;

                memo[t] = true;

                q.push( make_pair( times + 1, t ) );
                //cout << t << endl;
            }
        }

        // put
        if ( goal ) {
            cout << result_times << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}

C++: #include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

typedef pair <string,int> P;

int ans;
string str;

bool f(string s){
	for (int i=1; i<s.size(); i++) {
		if (s[0]!=s[i]) {
			return false;
		}
	}
	return true;
}

char c(char a,char b){
	if (a=='r'&&b=='g'||a=='g'&&b=='r') {
		return 'b';
	}
	else if (a=='r'&&b=='b'||a=='b'&&b=='r') {
		return 'g';
	}
	else {
		return 'r';
	}
}


bool bfs(){
	queue<P> que;
	map<string,int> mat;
	que.push(P(str,0));
	while (que.size()) {
		P p=que.front();
		que.pop();
		
		string s=p.first;
		int n=p.second+1;
		if (mat[s]) {
			continue;
		}
		
		if (f(s)) {
			ans=n-1;
			return true;
		}
		
		mat[s]=n;
		
		for (int i=0; i<s.size()-1; i++) {
			if (s[i]!=s[i+1]) {
				string t=s;
				char u=c(t[i],t[i+1]);
				t[i]=t[i+1]=u;
				que.push(P(t,n));
			}
		}
		
		
		
	}
	return false;
}

int main(){
	
	while (cin>>str&&str!="0") {
		if (bfs()) {
			cout << ans <<endl;
		}
		else {
			cout << "NA" <<endl;
		}
	}
	
}