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 <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

char change_color (char c1, char c2 )
{
	map<char, bool> used_color;
	used_color['r'] = false;
	used_color['g'] = false;
	used_color['b'] = false;

	used_color[c1] = true;
	used_color[c2] = true;

	map<char, bool>::iterator it = used_color.begin();
	for (; it != used_color.end(); ++it){
		if ( (*it).second == false ){
			return (*it).first;
		} // end if
	} // end for
} 
bool same_color (string s )
{
	int len = s.length();
	int n = (int)count (s.begin(), s.end(), s[0] );

	if (n == len ){
		return true;
	} // end if

	return false;
}	
	

int bfs (string str )
{
	int len = str.length();
	int i;

	queue <string> Q;
	string s = str;
	Q.push (s );
	set <string> S;
	multimap <string, string> D;

	while (!Q.empty() ){
		s = Q.front(); Q.pop();
//		cout << s << endl;
		if (same_color (s ) ){
			break;
		} // end if

		map<int, int> change_part;

		for (i = 0; i < len - 1; ++i){
			if (s[i] != s[i+1] ){
				change_part[i] = i+1;
			} // end if
		} // end for
		
		if (!change_part.empty() ){
			map<int, int>::iterator it = change_part.begin();
			for (; it != change_part.end(); ++it){
				string t = s;
				t[(*it).first] = change_color (s[(*it).first], s[(*it).second] );
				t[(*it).second] = change_color (s[(*it).first], s[(*it).second] );
				if (!S.count (t ) ){
					S.insert (t );
					Q.push (t );
					D.insert ( make_pair (t, s ) );
				} // end if
			} // end for
		} // end if
	} // end while

	if (Q.empty() && !same_color (s ) ){
		return -1;
	} // end if

	int res = 0;
	if (!D.empty() ){
		++res;
		multimap <string, string>::iterator it = D.begin();
		for (; it != D.end(); ++it){
			if ((*it).first == s ){
				 break;
			} // end if
		} // end for
		string from = (*it).second;
		while (from != str ){
			for (it = D.begin(); it != D.end(); ++it){
				if ( (*it).first == from ){
					from = (*it).second;
					++res;
					break;
				} // end if
			} // end for
		} // end while
	} // end if

	return res;	
}							 

int main()
{
//	cut here before submit 
//	freopen ("testcase.Mworm", "r", stdin );
	string str = "";
	int n;

	while (getline (cin, str ) ){
		int len = str.length();
		if (len == 1 && str[0] == '0'){
			break;
		} // end if
		int i;
		int res = 0;
		
		res = bfs (str );
		if (res == -1){
			cout << "NA" << endl;
		}else{
			cout << res << endl;	
		} // end if
	} // end loop
		
	return 0;
}

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

#define R 114
#define G 103
#define B 98

using namespace std;

class DATA{
	public:
		DATA(string temp){			//ÌzñÆzñÌ·³ðnµÄ °Ä­¾³¢
			step = 0;
			arr = temp;
		}
		
		DATA(string temp, int step) :arr(temp), step(step) {}
		
		//I¹»èH
		int check(void){
			char t = arr[0];
			for(int i = 0; i < arr.size(); i++){
				if(arr[i] != t){
					return 0;
				}
			}
			return 1;
		}
		
		int step;		//Xebv(JÚ)
		string arr;	//rgbÌÀÑ
};

//¦
int ans = -1;

int main()
{
	string rgb;
	string temp;
	int i,j, len;
	int temp3;
	char g;
	
	
	for(;;){
		
		set<string> table;

		cin >> rgb;
		if(rgb == "0"){
			break;
		}
		len = rgb.size();
		ans = -1;
		queue<DATA> Q;
		
		DATA start(rgb,0);
		
		Q.push(start);
		while(!Q.empty()){
			//`FbN·éf[^ðæèo·
			DATA d = Q.front();
			Q.pop();
			
			if(table.count(d.arr)){
				continue;
			}
			
			table.insert(d.arr);
			
			//I¹
			if(d.check() == 1){
				ans = d.step;
				break;
			}
			
			//·×ÄÌp^[ÉÎµÄóÔJÚµAL[Éi[
			for(i = 0; i < len-1; i++){
				temp = d.arr;
				if(d.arr[i] != d.arr[i+1]){
					switch(d.arr[i]+d.arr[i+1]){
						case R+B:
							temp[i] = temp[i+1]= G;
							break;
						case R+G:
							temp[i] = temp[i+1] = B;
							break;
						case G+B:
							temp[i] = temp[i+1] = R;
					}
					
					DATA next(temp,d.step+1);
					Q.push(next);
				}
			}
		}
		if(ans == -1){
			cout << "NA" << endl;
		}
		else{
			cout << ans << endl;
		}
	}
}